package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-19
 * Time: 下午1:11
 * To change this template use File | Settings | File Templates.
 */
public class N_Queens {
    public int RST=0;
    ArrayList<String[]> list = new ArrayList<String[]>();
    public boolean isSafe(int i,int j,int n,int[][] map){
        int k=-1;
        while(i+k>=0 && i+k<n && j+k>=0 && j+k<n)  //左上
        {
            if(map[i+k][j+k]==1)
                return false;
            k--;
        }
        k=1;
        while(i+k>=0 && i+k<n && j+k>=0 && j+k<n)  // 右下
        {
            if(map[i+k][j+k]==1)
                return false;
            k++;
        }
        k=-1;
        while(i+k>=0 && i+k<n && j-k>=0 && j-k<n) //  右上
        {
            if(map[i+k][j-k]==1)
                return false;
            k--;
        }
        k=1;
        while(i+k>=0 && i+k<n && j-k>=0 && j-k<n)//  左 下
        {
            if(map[i+k][j-k]==1)
                return false;
            k++;
        }
        return true;
    }
    public void find(int[][] map,int level,int n){
        int[] flag = new int[n];
        for(int i=0;i<level;i++){
            for(int j=0;j<n;j++)
                if(map[i][j]==1){
                    flag[j]=1;
                    break;
                }
        }
        if(level==n){
            RST++;
            String[] line = new String[n];
            for(int i=0;i<n;i++){
                String tmp = "";
                for(int j=0;j<n;j++){
                    if(map[i][j]==0)
                        tmp+=".";
                    else
                        tmp+="Q";
                }
                line[i] = tmp;
            }
            list.add(line);
        }
        for(int i=0;i<n;i++){
            if(flag[i]==0 && isSafe(level,i,n,map)){
                map[level][i]=1;
                find(map,level+1,n);
                map[level][i]=0;
            }
        }
    }
    public List<String[]> solveNQueens(int n) {
        int[][] map = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                map[i][j] = 0;
        }

        for(int i=0;i<n;i++){
            map[0][i]=1;
            find(map, 1, n);
            map[0][i]=0;
        }
        return list;
    }
    public static void main(String[] args){
        N_Queens n_queens = new N_Queens();
        System.out.println(n_queens.solveNQueens(4));
    }
}
